This invention relates in general to traffic analysis on packet networks. Packet networks are telecommunication networks in which the information is transmitted in small binary groups called packets. An advantage of packet networks is that it can handle different sources simultaneously by processing the packets sequentially. The packets travel through the network via a fast synchronous carrier; this can be viewed as a train of pulses which transport the packets. The speed of this carrier determines the maximum speed of the packet network. These networks can process only one packet at a time and thus the order in which the packets are processed depends on the priorities and quality of service required by the sources. Packets from a given source are mixed with packets from other sources. Each packet has a header that identifies its destination. Once the packets arrive at their destination, the headers are removed and the information is reassembled. Since these networks generally carry traffic from different types of sources which demand different service levels from the network, it is important from a network operation and management point of view to know the characteristics of the expected traffic. In the standards for packet networks that use the asynchronous transfer mode protocol (ATM), the traffic is described by first order statistics such as the peak cell rate, cell delay variation tolerance, sustainable cell rate, and maximum burst size. The size of the packets in ATM networks (that is networks which utilize the ATM protocol) is 53 bytes, of which 5 bytes compose the header and the remaining 48 bytes contain a section of the information being transmitted. The rate is defined as the number of packets that flow through the network in a given unit of time; this is a measure of the speed of the telecommunications network. The peak cell rate is defined as the inverse of the minimum time between successive packet arrivals to a switch. The cell delay variation tolerance is defined as the sensitivity of the information to changes in delay of the packets as they flow through the network. The sustainable cell rate is defined as the maximum average rate. The maximum burst size is defined as the maximum number of cells at the peak rate. Two of these parameters, the peak cell rate and the sustainable cell rate, have been defined as mandatory traffic parameters (or descriptors) in the ATM Forum UNI version 3.0 standards, as explained by McDysan and Spohn [11].
There are two types of networks which differ according to the way a connection is handled. The first type is connection-oriented. In these networks it is required to set up several parameters before any data transmission can take place. This is a process in which a source negotiates a level of service with the network. An end-to-end path with a quality of service is established and all the packets from the source will follow this path. The second type is connectionless in which it is not required to set up an end-to-end connection. The network handles the packets individually.
Quality of service (QoS) is a parameter meaningful from a source to a destination point of view, as well as at each link in the network. In connection-oriented networks, the negotiation for a QoS is carried out by agreeing on certain parameters. These parameters are based on first order statistical measures of the performance, such as the average delay, cell delay variation, error rates, and different levels of packet loss, as explained in the Bellcore requirements for broadband switching systems [2].
Packet networks have been designed to carry traffic from multimedia sources, among them different types of video and audio, voice, and data communications. Each traffic source presents the network with different requirements. The network must be able to handle all these traffic sources at their respective quality of service. The problem that arises is how to accurately characterize the different traffic sources for efficient network utilization. It might, in fact, be required to measure quality in different ways for different traffic sources. This makes the performance measurement problem very complex.
In our invention, a method is used to characterize the traffic in real-time. The method is used to calculate traffic descriptors considering properties of the traffic which have not been considered previously in commercial equipment. The descriptors are based on properties of the traffic that have been reported in the literature, but the techniques available are not suitable for real-time measurements. The algorithm presented is based on the simultaneous measurement of the traffic at different time scales. The data is represented in an appropriate form, processed and organized in an array of vectors. From this array, higher order statistical measures are derived. The traffic descriptors calculated in this way are used to characterize the traffic. The algorithm is implemented in real-time. The information is also used for traffic classification and performance prediction.
The following references have been identified in a search in this field, some of which are relevant to the present invention:
[1] R. Addie, M. Zukerman, and T. Neame, xe2x80x9cFractal Traffic: Measurements, Modelling and Performance Evaluationxe2x80x9d, in Proc. IEEE Infocom, pp. 977-984, 1995.
[2] Bellcore, xe2x80x9cBroadband Switching System Generic Requirementsxe2x80x9d, GR-1110-CORE, Revision 3, April 1996.
[3] J. Beran, R. Sherman, M. Taqqu, and W. Willinger, xe2x80x9cLong-Range Dependence In Variable-Bit-Rate Video Trafficxe2x80x9d, in IEEE Trans. on Communications, vol. 43, no. 4, pp. 1566-1579, April 1995.
[4] Y. Chen, Z. Deng, and C. Williamson, xe2x80x9cA Model for Self-Similar Ethernet LAN Traffic: Design, Implementation, and Performance Implicationsxe2x80x9d, internal report, University of Saskatchewan, Canada, 1995.
[5] M. Devetsikiotis, I. Lambadaris, R. Kaye, xe2x80x9cTraffic Modeling and Design Methodologies for Broadband Networksxe2x80x9d, Canadian Journal on Electrical and Computer Engineeringxe2x80x9d, vol. 20, no. 3, 1995.
[6] M. Garrett and W. Willinger, xe2x80x9cAnalysis, Modeling and Generation of Self-Similar VBR Video Trafficxe2x80x9d, in Proc. ACM Sigcom, London, UK, pp. 269-280, 1994.
[7] R. Guerin, H. Ahmadi and M. Naghshineh, xe2x80x9cEquivalent Capacity and its to Bandwidth Allocation in High Speed Networksxe2x80x9d, IEEE JSAC, vol. 9, no. 7, 1991.
[8] C. Huang, M. Devetsikiotis, I. Lambadaris, and A. Kaye, xe2x80x9cModeling and Simulation of Self-Similar Variable Bit Rate Compressed Video: A Unified Approachxe2x80x9d, in ACM Sigcom, Cambridge 1995.
[9] W. Lau, A. Erramilli, J. Wang, and W. Willinger, xe2x80x9cSelf-Similar Traffic Generation: The Random Midpoint Displacement Algorithm and its Propertiesxe2x80x9d, in Proc. IEEE Int Conf. Commun., 1995.
[10] W. Leland, M. Taqqu, W. Willinger, and D. Wilson, xe2x80x9cOn The Self-Similar Nature of Ethernet Traffic (extended version)xe2x80x9d, IEEE/ACM Trans. Networking, vol. 2, no. 1, pp. 1-15, February 1994.
[1] B. Mandelbrot, xe2x80x9cSelf-Similar Error Clusters in Communication Systems and the Concept of Conditional Stationarityxe2x80x9d, in IEEE Trans. on Communication Technology, pp. 71-90, 1965.
[12] D. McDysan and D. Spohn, xe2x80x9cATM Theory and Applicationxe2x80x9d. Toronto: McGraw-Hill, 1995.
[13] D. McLaren and D. Nguyen, xe2x80x9cA Fractal-Based Source Model for ATM Packet Videoxe2x80x9d, in Int. Conf. on Digital Processing of Signals in Communications, Univ. of Loughbovough, September 1991.
[14] V. Paxson, xe2x80x9cFast Approximation of Self-Similar Network Trafficxe2x80x9d, report LBL-36750, Univ. of California at Berkeley, Lawrence Berkeley Laboratory, 1995.
[15] A. Rueda and W. Kinsner, xe2x80x9cA Survey of Traffic Characterization Techniques in Telecommunication Networksxe2x80x9d, Proc. IEEE Canadian Conference on Electrical and Computer Engineering, pp. 830-833, May 1996.
U.S. Pat. No. 5,050,161 Congestion management based on multiple framing strategy
U.S. Pat. No. 5,274,625 Traffic measurements in packet communication networks
U.S. Pat. No. 5,341,366 Connection admission control system
U.S. Pat. No. 5,343,463 Performance measurement system for a telecommunication path and device used therein
U.S. Pat. No. 5,343,465 Method and system for real-time burstiness analysis of network traffic
U.S. Pat. No. 5,357,507 Fast connection admission control for ATM networks
U.S. Pat. No. 5,357,510 Apparatus and method for supervising and controlling ATM traffic
U.S. Pat. No. 5,365,514 Event driven interface for a system for monitoring and controlling a data communications network
U.S. Pat. No. 5,375,070 Information collection architecture and method for a data communications network
U.S. Pat. No. 5,394,394 Message header classifier
U.S. Pat. No. 5,426,635 Method for adaptive control of windows and rates in networks
U.S. Pat. No. 5,434,848 Traffic management in packet communication networks
U.S. Pat. No. 5,448,567 Control architecture for ATM networks
The traffic characterization techniques for telecommunication networks found in the literature can be classified into the following categories [5], [14]: autoregressive moving average (ARMA) models, Bernoulli process modeling, Markov chain modeling, neural network models, self-similar models, transform-expand-sample (TES) models, traffic flow models, and wavelet models.
Different kinds of stochastic (statistical) models reported in the literature have successfully been used in modeling traffic in telecommunication networks. For example, Markov chains are a useful tool in modeling communication systems. It is widely accepted that the short-term arrival processes in telecommunication networks can be accurately described by Poisson processes, for example an FTP control connection which can be modeled as a Markov modulated Poisson process (MMPP) [13].
Traffic on packet networks is irregular in nature as explained by Leland, et al. [9]. It is generally accepted that the long-range dependencies found in multimedia traffic can be described using models which consider self-similarity. Self-similarity is a measure of the variation of the traffic properties at different time scales. Several traffic models of this type have been reported [1], [4], [6], [7], [8], and [12].
The traffic descriptors that have been utilized in packet networks are based on statistical measures such as the mean, peak and sustained rates, burst length, and cell-loss ratios. These do not quantify correlation well, and thus a need exists for descriptors that provide more information in order to describe highly correlated and bursty (irregular) multimedia traffic [3] and [10].
Traditional analysis techniques cannot be successfully applied. The methods that have been proposed for the analysis of traffic in packet networks are impractical for a real-time implementation since they required calculations that involved several processing phases on a stored time series.
A method for time deviation (TDEV) calculation for synchronization monitoring in SONET/SDH networks is proposed by Grover and Stamatlakis [15]. Their method consists of the calculation of simultaneous averages of the second differences of time interval errors (TIE) at different time scales. A time scale is represented by blocks that contain a number of second differences which is a power of two. For each block the second differences are added and the result is squared. The sums of the squares are then divided by six and by a constant to obtain a measure called the time variance (TVAR) for the time scale. Each new TIE value produces a new second differences and this is used to updated all the block sums of all the time scales. Each new second difference could complete a block sum for one or more blocks and a new TVAR could be obtained. The results are used to produce a plot of the logarithm base two of the TVAR values of all the blocks versus the logarithm base two of the block size. Their paper also details the standard block calculation which consists of calculating the TVAR values for all the blocks in a batch mode (or block mode, or off-line). This consists of calculating the block sums and TVAR values of a time series of TIE values for each block separately.
[7] W. D. Grover and D. Stamatlakis, xe2x80x9cContinuous TDEV calculation for in-situ synchronisation monitoring in SONET/SDH networksxe2x80x9d, Electronic Letters, vol. 29, No. 16, pp. 1405-1406, August 1993.
Namajunas and Tamasevicius [16] proposed a device for measuring fractal dimensions from a time series in real-time. Their device is an electronic circuit that produces an approximation to the fractal dimension of a class of analog electric signals in real-time.
[8] A. Namajunas and A. Tamasevicius, xe2x80x9cA technique for measuring fractal dimensions from time series on a real-time scalexe2x80x9d, Physica D, vol. 58, pp. 482-488, 1992.
It is one object of the present invention to provide a method for characterizing transmissions in a packet network which may or may not be carried out in real time and may provide information which can be used to characterize the transmissions for prediction and access control.
According to a first aspect of the invention there is provided a method for deriving information related to characteristics of transmissions in a packet network comprising:
providing a packet network for carrying a plurality of transmissions from at least one source in which the transmissions from the or each source are divided into a plurality of sequential packets each packet having address data defining an intended address, information data defining information to be transmitted and id data defining a source identity;
the network defining a train of sequential packet transport locations into which packets are loaded for transmission, such that some packet transport locations in a train contain packets and some packet transport locations are empty and such that, when there is more than one different source, the train contains packets from the different sources in a sequential arrangement as determined by the network;
monitoring a train of packet transport locations to determine which packet transport locations are empty and which contain a packet;
generating a series of data elements each corresponding to a respective one of the packet transport locations and each identifying whether the respective packet transport location is empty or whether the respective packet transport location contains a packet;
and carrying out statistical analysis on the series of data elements to determine the characteristics of the transmissions.
Preferably the statistical analysis is carried out in real time so that predictions and characterization of the transmissions can be done in real time.
Preferably, as an alternative, the data elements are stored for example in the hard drive of a PC for subsequent analysis and the statistical analysis is carried out subsequent to completion of the transmissions when a series of transmissions have been recorded for analysis.
Preferably the statistical analysis is carried out at a plurality of different time scales in order to provide the calculations as set out hereinafter. Preferably the statistical analyses are carried out simultaneously by providing for each different time scale a respective one of a plurality of registers and entering information from the data elements into each register sequentially.
Preferably, in a simple single mode, the data elements comprise data bits defining xe2x80x9c0xe2x80x9d when the respective packet transport location is empty and xe2x80x9c1xe2x80x9d when the respective packet transport location contains a packet and wherein the information for each register is obtained by adding the contents of a next adjacent previous register.
Using the data bits, the analysis includes, for each register, calculating the sample variance of a set of successive observations of the register contents and from the variances estimating a value of the Hurst parameter H, which is the slope of a line which approximates the behavior of a plot of the logarithm of the variances of the registers versus the values of the sequential indices of the registers. This parameter is known per se but the present algorithm provides a technique for calculating this parameter in real time.
When the packets in the train are provided by a plurality of different sources the data elements are arranged to identify a packet transport location as containing a packet only when the packet is identified from the id data as provided by a selected one of the sources such that the characteristics determined relate to only the transmissions from the selected source.
When the packets in the train are provided by a plurality of different sources the data elements are arranged to identify a packet transport location as empty when no packet from any of the sources is contained and to identify when a packet transport location contains a packet from the id data as provided by each one of the sources which source provided the packet.
The characteristics determined from the data elements can be used to provide a calculation of an effective bandwidth of the transmissions for use in access control and prediction.
In particular the above method can be used in one example for determining whether a source additional to a plurality of existing sources of packet transmissions, each source having a predetermined peak rate of packet transmission, can be connected to a packet network, where a transmission medium of the network has a predetermined maximum allowable peak rate of transmissions. This is preferable effected by the steps of:
carrying out in real time the statistical analysis on the series of data elements to determine an effective bandwidth of the transmissions from the existing sources;
and calculating whether the additional source can be connected by comparing the effective bandwidth, the predetermined peak rate of packet transmission of the additional source and the predetermined maximum allowable peak rate of transmissions of the transmission medium of the network.
As an alternative, the method can be used for calculating whether a source additional to a plurality of existing sources of packet transmissions, each source having a predetermined peak rate of packet transmission, can be connected to a second packet network, a transmission medium of the second packet network having a predetermined maximum allowable peak rate of transmissions. This is effected by the steps of:
connecting the additional source to the packet network;
generating said series of data elements from transmissions from said additional source to said packet network;
carrying out in real time the statistical analysis on the series of data elements to determine an effective bandwidth of the transmissions from said additional source;
and calculating whether the additional source can be connected to the second packet network by using the effective bandwidth of the transmissions from said additional source.
According to a second aspect of the invention there is provided a method for deriving information related to the characteristics of transmissions in a packet network comprising:
providing a packet network for carrying a plurality of transmissions from at least one source in which the transmissions from the or each source are divided into a plurality of sequential packets each packet having address data defining an intended address, information data defining information to be transmitted and id data defining a source identity;
the network defining a train of sequential packet transport locations into which packets are loaded for transmission, such that some packet transport locations in a train contain packets and some packet transport locations are empty and such that, when there is more than one different source, the train contains packets from the different sources in a sequential arrangement as determined by the network;
monitoring a train of packet transport locations to determine which packet transport locations are empty and which contain a packet;
generating information defining which packet transport locations contain a packet and the empty locations therebetween;
and carrying out simultaneously and in real time a series of statistical analyses on the information at a plurality of different time scales to determine the characteristics of the transmissions.
In this aspect, the information is not necessarily the data bits as set forth above but can include other information relating to the population of the packets. However in this aspect, the analysis is effected in real time. Preferably however as explained in detail hereinafter, the information comprises a series of data elements each corresponding to a respective one of the packet transport locations and each identifying whether the respective packet transport location is empty or whether the respective packet transport location contains a packet and wherein the statistical analyses are carried out by providing for each different time scale a respective one of a plurality of registers and entering information from the data elements into each register sequentially.
More preferably the data elements comprise bits which define xe2x80x9c0xe2x80x9d when the respective packet transport location is empty and xe2x80x9c1xe2x80x9d when the respective packet transport location contains a packet and wherein the information for each register is obtained by adding the contents of a next adjacent previous register.
According to a third aspect of the present invention the same technique for generating bits relating to the empty and filled packets can be used in reverse in a method of generating packet transmissions for simulating a source having required transmission characteristics for transmitting on a packet network comprising:
providing a packet network for carrying a plurality of transmissions from at least one source in which the transmissions from the or each source are divided into a plurality of sequential packets each packet having address data defining an intended address, information data defining information to be transmitted and id data defining a source identity;
the network defining trains of sequential packet transport locations into which packets are loaded for transmission, such that some packet transport locations in a train contain packets and some packet transport locations are empty and such that, when there is more than one different source, the train contains packets from the different sources in a sequential arrangement as determined by the network;
from a statistical analysis of previous actual transmissions on the network, generating for the simulated source the required characteristic;
generating from the required characteristic a series of data elements each corresponding to a respective one of the packet transport locations and each specifying whether, in a simulated train of packets, a respective packet transport location is empty or whether the respective packet transport location contains a packet;
and creating from the data elements the simulated packet train.
Thus as set forth above, a methodology is disclosed for real-time traffic analysis, characterization, prediction, and classification in packet networks. The methodology is based on the simultaneous aggregation of packet arrival times at different time scales. The traffic is represented at the synchronous carrier level by the arrival or non-arrival of a packet. The invention does not require knowledge about the source, nor needs to decode the information contents of the packets. Only the arrival timing information is required. The binary representation of the traffic, that is, the arrival or non-arrival indicator, is processed by a series of processing units and organized in an array of vectors. The processing units are arranged in a series in such a way that the each processing unit operates with the result from the previous unit. The first processing unit operates directly with the timing information. The results of all the processing units are organized in the array of vectors and from these vectors information about the traffic can be derived. Statistical measures on the vectors such as variance, provide appropriate parameters at different time scales to calculate traffic descriptors. These descriptors encapsulate different properties of the traffic, such as burstiness and self-similarity, which were previously not considered in traffic management on packet networks.
A characterization is obtained of the traffic on packet networks suitable for a real-time implementation. The methodology can be applied in real-time traffic classification by training a neural network from calculated second order statistics of the traffic of several known sources. Performance descriptors for the network can also be obtained by calculating the deviation of the traffic distribution from calculated models. Traffic prediction can also be done by training a neural network from a vector of the results of a given processing against a vector of results of the subsequent processing unit; noticing that the later vector contains information at a larger time scale than the previous. The data produced by the algorithm can also be used for performance prediction.